[算法总结] 搞定 BAT 面试——几道常见的子符串算法题

说明

• 本文作者：

  wwwxmu

• 原文地址:

  https://www.weiweiblog.cn/13string/

• 作者的博客站点（推荐哦！）：

  https://www.weiweiblog.cn/ 

考虑到篇幅问题，我会分两次更新这个内容。本篇文章只是原文的一部分，我在原文的基础上增加了部分内容以及修改了部分代码和注释。另外，我增加了爱奇艺 2018 秋招 Java： 求给定合法括号序列的深度 这道题。所有代码均编译成功，并带有注释，欢迎各位享用！

1. KMP 算法

谈到字符串问题，不得不提的就是 KMP 算法，它是用来解决字符串查找的问题，可以在一个字符串（S）中查找一个子串（W）出现的位置。KMP 算法把字符匹配的时间复杂度缩小到 O(m+n) ,而空间复杂度也只有O(m)。因为“暴力搜索”的方法会反复回溯主串，导致效率低下，而KMP算法可以利用已经部分匹配这个有效信息，保持主串上的指针不回溯，通过修改子串的指针，让模式串尽量地移动到有效的位置。

具体算法细节请参考：

• 字符串匹配的KMP算法:http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

• 从头到尾彻底理解KMP: https://blog.csdn.net/vjulyv/article/details/7041827

• 如何更好的理解和掌握 KMP 算法?: https://www.zhihu.com/question/21923021

• KMP 算法详细解析: https://blog.sengxian.com/algorithms/kmp

• 图解 KMP 算法: http://blog.jobbole.com/76611/

• 汪都能听懂的KMP字符串匹配算法【双语字幕】: https://www.bilibili.com/video/av3246487/?from=search&seid=17173603269940723925

• KMP字符串匹配算法1: https://www.bilibili.com/video/av11866460?from=search&seid=12730654434238709250

除此之外，再来了解一下BM算法！

BM算法也是一种精确字符串匹配算法，它采用从右向左比较的方法，同时应用到了两种启发式规则，即坏字符规则 和好后缀规则 ，来决定向右跳跃的距离。基本思路就是从右往左进行字符匹配，遇到不匹配的字符后从坏字符表和好后缀表找一个最大的右移值，将模式串右移继续匹配。 《字符串匹配的KMP算法》:http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

2. 替换空格

剑指offer：请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

这里我提供了两种方法：①常规方法；②利用 API 解决。

1. //https://www.weiweiblog.cn/replacespace/

2. public class Solution {

3.    /**

4.     * 第一种方法：常规方法。利用String.charAt(i)以及String.valueOf(char).equals(" "

5.     * )遍历字符串并判断元素是否为空格。是则替换为"%20",否则不替换

6.     */

7.    public static String replaceSpace(StringBuffer str) {

8.        int length = str.length();

9.        // System.out.println("length=" + length);

10.        StringBuffer result = new StringBuffer();

11.        for (int i = 0; i < length; i++) {

12.            char b = str.charAt(i);

13.            if (String.valueOf(b).equals(" ")) {

14.                result.append("%20");

15.            } else {

16.                result.append(b);

17.            }

18.        }

19.        return result.toString();

20.    }

21.    /**

22.     * 第二种方法：利用API替换掉所用空格，一行代码解决问题

23.     */

24.    public static String replaceSpace2(StringBuffer str) {

25.        return str.toString().replaceAll("\\s", "%20");

26.    }

27. }

3. 最长公共前缀

Leetcode: 编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。

示例 1:

1. 输入: ["flower","flow","flight"]

2. 输出: "fl"

示例 2:

1. 输入: ["dog","racecar","car"]

2. 输出: ""

3. 解释: 输入不存在公共前缀。

思路很简单！先利用Arrays.sort(strs)为数组排序，再将数组第一个元素和最后一个元素的字符从前往后对比即可！

1. //https://leetcode-cn.com/problems/longest-common-prefix/description/

2. public class Main {

3.    public static String replaceSpace(String[] strs) {

4.        // 数组长度

5.        int len = strs.length;

6.        // 用于保存结果

7.        StringBuffer res = new StringBuffer();

8.        // 注意：=是赋值，==是判断

9.        if (strs == null || strs.length == 0) {

10.            return "";

11.        }

12.        // 给字符串数组的元素按照升序排序(包含数字的话，数字会排在前面)

13.        Arrays.sort(strs);

14.        int m = strs[0].length();

15.        int n = strs[len - 1].length();

16.        int num = Math.min(m, n);

17.        for (int i = 0; i < num; i++) {

18.            if (strs[0].charAt(i) == strs[len - 1].charAt(i)) {

19.                res.append(strs[0].charAt(i));

20.            } else

21.                break;

22.        }

23.        return res.toString();

24.    }

25.     //测试

26.    public static void main(String[] args) {

27.        String[] strs = { "customer", "car", "cat" };

28.        System.out.println(Main.replaceSpace(strs));//c

29.    }

30. }

4. 回文串

4.1. 最长回文串

LeetCode: 给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。在构造过程中，请注意区分大小写。比如 "Aa"不能当做一个回文字符串。注 意:假设字符串的长度不会超过 1010。

回文串：“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。——百度百科 地址：https://baike.baidu.com/item/%E5%9B%9E%E6%96%87%E4%B8%B2/1274921?fr=aladdin

示例 1:

1. 输入:

2. "abccccdd"

3. 输出:

4. 7

5. 解释:

6. 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

我们上面已经知道了什么是回文串？现在我们考虑一下可以构成回文串的两种情况：

• 字符出现次数为双数的组合

• 字符出现次数为双数的组合+一个只出现一次的字符

统计字符出现的次数即可，双数才能构成回文。因为允许中间一个数单独出现，比如“abcba”，所以如果最后有字母落单，总长度可以加 1。首先将字符串转变为字符数组。然后遍历该数组，判断对应字符是否在hashset中，如果不在就加进去，如果在就让count++，然后移除该字符！这样就能找到出现次数为双数的字符个数。

1. //https://leetcode-cn.com/problems/longest-palindrome/description/

2. class Solution {

3.    public  int longestPalindrome(String s) {

4.        if (s.length() == 0)

5.            return 0;

6.        // 用于存放字符

7.        HashSet<Character> hashset = new HashSet<Character>();

8.        char[] chars = s.toCharArray();

9.        int count = 0;

10.        for (int i = 0; i < chars.length; i++) {

11.            if (!hashset.contains(chars[i])) {// 如果hashset没有该字符就保存进去

12.                hashset.add(chars[i]);

13.            } else {// 如果有,就让count++（说明找到了一个成对的字符），然后把该字符移除

14.                hashset.remove(chars[i]);

15.                count++;

16.            }

17.        }

18.        return hashset.isEmpty() ? count * 2 : count * 2 + 1;

19.    }

20. }

4.2. 验证回文串

LeetCode: 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。 说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:

1. 输入: "A man, a plan, a canal: Panama"

2. 输出: true

示例 2:

1. 输入: "race a car"

2. 输出: false

1. //https://leetcode-cn.com/problems/valid-palindrome/description/

2. class Solution {

3.    public  boolean isPalindrome(String s) {

4.        if (s.length() == 0)

5.            return true;

6.        int l = 0, r = s.length() - 1;

7.        while (l < r) {

8.            // 从头和尾开始向中间遍历

9.            if (!Character.isLetterOrDigit(s.charAt(l))) {// 字符不是字母和数字的情况

10.                l++;

11.            } else if (!Character.isLetterOrDigit(s.charAt(r))) {// 字符不是字母和数字的情况

12.                r--;

13.            } else {

14.                // 判断二者是否相等

15.                if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r)))

16.                    return false;

17.                l++;

18.                r--;

19.            }

20.        }

21.        return true;

22.    }

23. }

4.3. 最长回文子串

Leetcode: LeetCode: 最长回文子串 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

示例 1：

1. 输入: "babad"

2. 输出: "bab"

3. 注意: "aba"也是一个有效答案。

示例 2：

1. 输入: "cbbd"

2. 输出: "bb"

以某个元素为中心，分别计算偶数长度的回文最大长度和奇数长度的回文最大长度。给大家大致花了个草图，不要嫌弃！

1. //https://leetcode-cn.com/problems/longest-palindromic-substring/description/

2. class Solution {

3.    private int index, len;

4.    public String longestPalindrome(String s) {

5.        if (s.length() < 2)

6.            return s;

7.        for (int i = 0; i < s.length() - 1; i++) {

8.            PalindromeHelper(s, i, i);

9.            PalindromeHelper(s, i, i + 1);

10.        }

11.        return s.substring(index, index + len);

12.    }

13.    public void PalindromeHelper(String s, int l, int r) {

14.        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {

15.            l--;

16.            r++;

17.        }

18.        if (len < r - l - 1) {

19.            index = l + 1;

20.            len = r - l - 1;

21.        }

22.    }

23. }

4.4. 最长回文子序列

LeetCode: 最长回文子序列 给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。最长回文子序列和上一题最长回文子串的区别是，子串是字符串中连续的一个序列，而子序列是字符串中保持相对位置的字符序列，例如，"bbbb"可以是字符串"bbbab"的子序列但不是子串。

给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。

示例 1:

1. 输入:

2. "bbbab"

3. 输出:

4. 4

一个可能的最长回文子序列为 "bbbb"。

示例 2:

1. 输入:

2. "cbbd"

3. 输出:

4. 2

一个可能的最长回文子序列为 "bb"。

动态规划： dp[i][j] = dp[i+1][j-1] + 2 if s.charAt(i) == s.charAt(j) otherwise, dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])

1. class Solution {

2.    public int longestPalindromeSubseq(String s) {

3.        int len = s.length();

4.        int [][] dp = new int[len][len];

5.        for(int i = len - 1; i>=0; i--){

6.            dp[i][i] = 1;

7.            for(int j = i+1; j < len; j++){

8.                if(s.charAt(i) == s.charAt(j))

9.                    dp[i][j] = dp[i+1][j-1] + 2;

10.                else

11.                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);

12.            }

13.        }

14.        return dp[0][len-1];

15.    }

16. }

5. 括号匹配深度

爱奇艺 2018 秋招 Java： 一个合法的括号匹配序列有以下定义:

1. 空串""是一个合法的括号匹配序列

2. 如果"X"和"Y"都是合法的括号匹配序列,"XY"也是一个合法的括号匹配序列

3. 如果"X"是一个合法的括号匹配序列,那么"(X)"也是一个合法的括号匹配序列

4. 每个合法的括号序列都可以由以上规则生成。

例如: "","()","()()","((()))"都是合法的括号序列 对于一个合法的括号序列我们又有以下定义它的深度:

1. 空串""的深度是0

2. 如果字符串"X"的深度是x,字符串"Y"的深度是y,那么字符串"XY"的深度为max(x,y)

3. 如果"X"的深度是x,那么字符串"(X)"的深度是x+1

例如: "()()()"的深度是1,"((()))"的深度是3。牛牛现在给你一个合法的括号序列,需要你计算出其深度。

1. 输入描述:

2. 输入包括一个合法的括号序列s,s长度length(2 ≤ length ≤ 50),序列中只包含'('和')'。

3. 输出描述:

4. 输出一个正整数,即这个序列的深度。

示例：

1. 输入:

2. (())

3. 输出:

4. 2

思路草图：

代码如下：

1. import java.util.Scanner;

2. /**

3. * https://www.nowcoder.com/test/8246651/summary

4. *

5. * @author Snailclimb

6. * @date 2018年9月6日

7. * @Description: TODO 求给定合法括号序列的深度

8. */

9. public class Main {

10.    public static void main(String[] args) {

11.        Scanner sc = new Scanner(System.in);

12.        String s = sc.nextLine();

13.        int count= 0, max = 0, i;

14.        for (i = 0; i < s.length(); ++i) {

15.            if (s.charAt(i) == '(')

16.                count++;

17.            else

18.                count--;

19.            max = Math.max(max, count);

20.        }

21.        sc.close();

22.        System.out.println(max);

23.    }

24. }

6. 把字符串转换成整数

剑指offer: 将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。

1. //https://www.weiweiblog.cn/strtoint/

2. public class Main {

3.    public static int StrToInt(String str) {

4.        if (str.length() == 0)

5.            return 0;

6.        char[] chars = str.toCharArray();

7.        // 判断是否存在符号位

8.        int flag = 0;

9.        if (chars[0] == '+')

10.            flag = 1;

11.        else if (chars[0] == '-')

12.            flag = 2;

13.        int start = flag > 0 ? 1 : 0;

14.        int res = 0;// 保存结果

15.        for (int i = start; i < chars.length; i++) {

16.            if (Character.isDigit(chars[i])) {// 调用Character.isDigit(char)方法判断是否是数字，是返回True，否则False

17.                int temp = chars[i] - '0';

18.                res = res * 10 + temp;

19.            } else {

20.                return 0;

21.            }

22.        }

23.        return flag == 1 ? res : -res;

24.    }

25.    public static void main(String[] args) {

26.        // TODO Auto-generated method stub

27.        String s = "-12312312";

28.        System.out.println("使用库函数转换：" + Integer.valueOf(s));

29.        int res = Main.StrToInt(s);

30.        System.out.println("使用自己写的方法转换：" + res);

31.    }

32. }

推荐阅读：

如果觉得文章不错，欢迎转发点赞。你的转发与点赞就是我原创最大的动力！

点赞点广告会增加面试通过几率哦！（据说会有锦鲤庇佑！啦啦啦~）